package com.xx.springboot.DataStructure.LeetCode.Array;

/**
     判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

     数字 1-9 在每一行只能出现一次。
     数字 1-9 在每一列只能出现一次。
     数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。


     上图是一个部分填充的有效的数独。

     数独部分空格内已填入了数字，空白格用 '.' 表示。

     示例 1:

     输入:
     [
     ["5","3",".",".","7",".",".",".","."],
     ["6",".",".","1","9","5",".",".","."],
     [".","9","8",".",".",".",".","6","."],
     ["8",".",".",".","6",".",".",".","3"],
     ["4",".",".","8",".","3",".",".","1"],
     ["7",".",".",".","2",".",".",".","6"],
     [".","6",".",".",".",".","2","8","."],
     [".",".",".","4","1","9",".",".","5"],
     [".",".",".",".","8",".",".","7","9"]
     ]
     输出: true
     示例 2:

     输入:
     [
     ["8","3",".",".","7",".",".",".","."],
     ["6",".",".","1","9","5",".",".","."],
     [".","9","8",".",".",".",".","6","."],
     ["8",".",".",".","6",".",".",".","3"],
     ["4",".",".","8",".","3",".",".","1"],
     ["7",".",".",".","2",".",".",".","6"],
     [".","6",".",".",".",".","2","8","."],
     [".",".",".","4","1","9",".",".","5"],
     [".",".",".",".","8",".",".","7","9"]
     ]
     输出: false
     解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
     说明:

     一个有效的数独（部分已被填充）不一定是可解的。
     只需要根据以上规则，验证已经填入的数字是否有效即可。
     给定数独序列只包含数字 1-9 和字符 '.' 。
     给定数独永远是 9x9 形式的。
 */
public class isValidSudoku {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if(board[i][j] == '.')
                    continue;

                if(!isVaild(board , i, j))
                    return false;

            }
        }

        return true;
    }

    public boolean isVaild(char[][] board, int x, int y) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // 判断横向
                if (i == x && j != y && board[i][j] == board[x][y])
                    return false;


                // 判断纵向
                if (j == y && i != x && board[i][j] == board[x][y])
                    return false;

                // 判断九宫格

                for (int lx = x - (x % 3); lx < ((x - (x % 3)) + 3); lx ++) {
                    for (int ly = y - (y % 3); ly < ((y - (y % 3)) + 3); ly ++) {
                        if(lx != x && ly != y && board[x][y] == board[lx][ly])
                            return false;
                    }
                }

            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] chars = {  {'3','.','.','.','.','4','.','.','.'},
                            {'.','.','.','.','1','.','8','.','.'},
                            {'.','7','2','.','.','.','.','.','.'},
                            {'.','.','5','.','.','.','.','.','.'},
                            {'.','4','.','.','.','.','.','.','.'},
                            {'.','.','.','.','.','.','3','.','.'},
                            {'.','.','.','.','.','.','.','.','1'},
                            {'1','3','.','.','.','5','.','.','.'},
                            {'.','.','.','.','5','.','.','2','.'}
                        };

        isValidSudoku isValidSudoku = new isValidSudoku();
        System.out.println(isValidSudoku.isValidSudoku(chars));;
    }
}
